Feature #8: Optimal Path

Description#

Uber is one of the most popular ride-hailing applications. It provides a choice of a variety of vehicles to the passengers that use it for transport. Uber always uses an optimal path to save its passenger’s time. The terrain is represented as a 2D grid. A passenger waits on one end of the grid and a driver is present on another end. This feature will show us how to find the optimal path for the driver to get to the passenger.

Solution#

A new path metric is evaluated. The terrain is represented as a 2D grid, and the cost of going from one point to an adjacent one is given as an integer.

Here is how the implementation of this feature will take place:

1. We can think of this problem as a shortest path problem in a 2D rectangular graph, where the values in the input array are edge weights.

2. Since the driver can only travel right or downward, the optimal way to get to any of the cells in the first row is to travel right. Thus, we can iteratively calculate the costs along the first row as $cost[0][i] = cost[0][i] + cost[0][i-1]$ for all $i = 1, 2,$ …, $n-1$. This process will apply to the highlighted cells below.

3. Similarly, the optimal cost to every cell in the first column can be computed as $cost[j][0] = cost[j][0] + cost[j-1][0]$ for all $j$ = $1, 2,$ …, $m-1$. This process will apply to the highlighted cells below.

4. All other cells can be reached either from the cell above or from the cell to the left. We will pick the option that has the least cost. Thus, $cost[i][j] = min(cost[i-1][j], cost[i][j-1]) + cost[i][j]$ for $i = 1, 2,$ …, $n-1$ and $j = 1, 2,$ …, $m-1$. This process will apply to the highlighted cells below.

5. Finally, cost[m][n] will have the cost of the optimal path from the driver to the waiting passenger.

The following slides illustrate this process:

Let’s look at the code for this solution:

Complexity measures#

Time complexity#

We will traverse the entire matrix only once. Therefore, the time complexity will be $O(mn)$, where $m$ will represent the number of rows and $n$ will represent the number of columns.

Space complexity#

We will compute the minimum path sum in place. Therefore, the space complexity will be $O(1)$.